package Graph;

import java.util.Vector;

/**
 * @author chetaifu
 * 邻接表
 */
public class SparseGraph implements Graph{
    /**
     * 节点数
     */
    private int n;

    /**
     * 边数
     */
    private int m;

    /**
     * 是否为有向图
     */
    private boolean directed;

    /**
     * 图的具体数据
     */
    private Vector<Integer>[] g;

    public SparseGraph(int n, boolean directed) {
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = (Vector<Integer>[]) new Vector[n];
        for(int i = 0 ; i < n ; i ++){
            g[i] = new Vector<>();
        }

    }

    @Override
    public int V() {
        return n;
    }

    @Override
    public int E() {
        return m;
    }

    @Override
    public void addEdge(int v, int w) {
        assert (v >= 0 && v < n);
        assert (w >= 0 && w < n);

        g[v].add(w);
        if(v != w && !directed){
            g[w].add(v);
        }
        m ++;
    }

    @Override
    public boolean hasEdge(int v, int w) {
        assert (v >= 0 && v < n);
        assert (w >= 0 && w < n);

        for(int i = 0; i < g[v].size(); i ++){
            if(g[v].elementAt(i) == w){
                return true;
            }
        }
        return false;
    }

    @Override
    public void show() {

    }

    @Override
    public Iterable<Integer> iterate(int v) {
        assert (v >= 0 && v < n);
        return g[v];
    }
}
